Memory consistency directed cache coherence protocols for scalable multiprocessors

摘要

The memory consistency model, which formally specifies the behavior of the\udmemory system, is used by programmers to reason about parallel programs. From a\udhardware design perspective, weaker consistency models permit various optimizations\udin a multiprocessor system: this thesis focuses on designing and optimizing the cache\udcoherence protocol for a given target memory consistency model.\udTraditional directory coherence protocols are designed to be compatible with the\udstrictest memory consistency model, sequential consistency (SC). When they are used\udfor chip multiprocessors (CMPs) that provide more relaxed memory consistency models,\udsuch protocols turn out to be unnecessarily strict. Usually, this comes at the cost of\udscalability, in terms of per-core storage due to sharer tracking, which poses a problem\udwith increasing number of cores in today’s CMPs, most of which no longer are sequentially\udconsistent. The recent convergence towards programming language based relaxed\udmemory consistency models has sparked renewed interest in lazy cache coherence\udprotocols. These protocols exploit synchronization information by enforcing coherence\udonly at synchronization boundaries via self-invalidation. As a result, such protocols do\udnot require sharer tracking which benefits scalability. On the downside, such protocols\udare only readily applicable to a restricted set of consistency models, such as Release\udConsistency (RC), which expose synchronization information explicitly. In particular,\udexisting architectures with stricter consistency models (such as x86) cannot readily\udmake use of lazy coherence protocols without either: adapting the protocol to satisfy\udthe stricter consistency model; or changing the architecture’s consistency model to (a\udvariant of) RC, typically at the expense of backward compatibility. The first part of\udthis thesis explores both these options, with a focus on a practical approach satisfying\udbackward compatibility.\udBecause of the wide adoption of Total Store Order (TSO) and its variants in x86 and\udSPARC processors, and existing parallel programs written for these architectures, we\udfirst propose TSO-CC, a lazy cache coherence protocol for the TSO memory consistency\udmodel. TSO-CC does not track sharers and instead relies on self-invalidation and\uddetection of potential acquires (in the absence of explicit synchronization) using per\udcache line timestamps to efficiently and lazily satisfy the TSO memory consistency\udmodel. Our results show that TSO-CC achieves, on average, performance comparable\udto a MESI directory protocol, while TSO-CC’s storage overhead per cache line scales\udlogarithmically with increasing core count.\udNext, we propose an approach for the x86-64 architecture, which is a compromise\udbetween retaining the original consistency model and using a more storage efficient\udlazy coherence protocol. First, we propose a mechanism to convey synchronization\udinformation via a simple ISA extension, while retaining backward compatibility with\udlegacy codes and older microarchitectures. Second, we propose RC3 (based on TSOCC),\uda scalable cache coherence protocol for RCtso, the resulting memory consistency\udmodel. RC3 does not track sharers and relies on self-invalidation on acquires. To\udsatisfy RCtso efficiently, the protocol reduces self-invalidations transitively using per-L1\udtimestamps only. RC3 outperforms a conventional lazy RC protocol by 12%, achieving\udperformance comparable to a MESI directory protocol for RC optimized programs.\udRC3’s storage overhead per cache line scales logarithmically with increasing core count\udand reduces on-chip coherence storage overheads by 45% compared to TSO-CC.\udFinally, it is imperative that hardware adheres to the promised memory consistency\udmodel. Indeed, consistency directed coherence protocols cannot use conventional coherence\uddefinitions (e.g. SWMR) to be verified against, and few existing verification\udmethodologies apply. Furthermore, as the full consistency model is used as a specification,\udtheir interaction with other components (e.g. pipeline) of a system must not be\udneglected in the verification process. Therefore, verifying a system with such protocols\udin the context of interacting components is even more important than before. One\udcommon way to do this is via executing tests, where specific threads of instruction\udsequences are generated and their executions are checked for adherence to the consistency\udmodel. It would be extremely beneficial to execute such tests under simulation,\udi.e. when the functional design implementation of the hardware is being prototyped.\udMost prior verification methodologies, however, target post-silicon environments, which\udwhen used for simulation-based memory consistency verification would be too slow.\udWe propose McVerSi, a test generation framework for fast memory consistency\udverification of a full-system design implementation under simulation. Our primary\udcontribution is a Genetic Programming (GP) based approach to memory consistency test\udgeneration, which relies on a novel crossover function that prioritizes memory operations\udcontributing to non-determinism, thereby increasing the probability of uncovering\udmemory consistency bugs. To guide tests towards exercising as much logic as possible,\udthe simulator’s reported coverage is used as the fitness function. Furthermore, we\udincrease test throughput by making the test workload simulation-aware. We evaluate\udour proposed framework using the Gem5 cycle accurate simulator in full-system mode\udwith Ruby (with configurations that use Gem5’s MESI protocol, and our proposed\udTSO-CC together with an out-of-order pipeline). We discover 2 new bugs in the MESI\udprotocol due to the faulty interaction of the pipeline and the cache coherence protocol,\udhighlighting that even conventional protocols should be verified rigorously in the\udcontext of a full-system. Crucially, these bugs would not have been discovered through\udindividual verification of the pipeline or the coherence protocol. We study 11 bugs\udin total. Our GP-based test generation approach finds all bugs consistently, therefore\udproviding much higher guarantees compared to alternative approaches (pseudo-random\udtest generation and litmus tests).